package zuo.algo.c16;

/**
 * 正数数组arr包含了一堆硬币，给定一个值n，求组成n的最小硬币数
 */
public class CoinsMin {

    /**
     * 01:00
     */
    public static int exc1(int[] arr, int n) {
        return process1(arr, 0, n);
    }

    public static int process1(int[] arr, int idx, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (rest == 0) {
            return 0;
        }
        if (idx == arr.length) {
            return -1;
        }
        int res1 = process1(arr, idx + 1, rest - arr[idx]);
        int res2 = process1(arr, idx + 1, rest);
        if (res1 < 0) {
            return res2;
        }
        res1 += 1;
        if (res2 < 0) {
            return res1;
        }
        return Math.min(res1, res2);
    }

    /**
     * 01:24
     */
    public static int exc2(int[] arr, int n) {
        int[][] dp = new int[arr.length + 1][n + 1];
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -2;
            }
        }
        return process2(arr, 0, n, dp);
    }

    private static int process2(int[] arr, int idx, int rest, int[][] dp) {
        if (rest < 0) {
            return -1;
        }
        if (dp[idx][rest] != -2) {
            return dp[idx][rest];
        }
        if (rest == 0) {
            dp[idx][rest] = 0;
        } else if (idx == arr.length) {
            dp[idx][rest] = -1;
        } else {
            int res1 = process2(arr, idx + 1, rest - arr[idx], dp);
            int res2 = process2(arr, idx + 1, rest, dp);
            if (res1 < 0) {
                dp[idx][rest] = res2;
            } else if (res2 < 0) {
                dp[idx][rest] = res1 + 1;
            } else {
                dp[idx][rest] = Math.min(res1, res2);
            }
        }
        return dp[idx][rest];
    }
}
